package top.dprkshow.practice.bst;

/**
 * @author Kent HAN
 * @date 2021/8/22
 */
public class Bst {

    static class Node {
        int data;
        Node left, right;
    }

    static Node insert(Node root, int data) {
        if (root == null) {
            Node newNode = new Node();
            newNode.data = data;
            root = newNode;
        } else if (data < root.data) {
            root.left = insert(root.left, data);
        } else {
            root.right = insert(root.right, data);
        }
        return root;
    }

    static boolean isInTree(Node root, int data) {
        if (root == null) {
            return false;
        }
        if (data == root.data) {
            return true;
        } else if (data < root.data) {
            return isInTree(root.left, data);
        } else {
            return isInTree(root.right, data);
        }
    }

    static int getMin (Node root) {
        if (root == null) {
            throw new RuntimeException("Tree is empty.");
        }
        if (root.left == null) {
            return root.data;
        } else {
            return getMin(root.left);
        }
    }

    static int getMax(Node root) {
        if (root == null) {
            throw new RuntimeException("Tree is empty.");
        }
        if (root.right == null) {
            return root.data;
        } else {
            return getMax(root.right);
        }
    }

    static int getHeight(Node root) {
        if (root == null) {
            return -1;
        }
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }

    static boolean isBst(Node root) {
        return isBetween(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    static boolean isBetween(Node root, int min, int max) {
        if (root == null) {
            return true;
        }
        return root.data > min && root.data < max && isBetween(root.left, min, root.data)
                && isBetween(root.right, root.data, max);
    }

    static Node delete(Node root, int data) {
        if (root == null) {
            return root;
        }
        if (data < root.data) {
            root.left = delete(root.left, data);
        } else if (data > root.data) {
            root.right = delete(root.right, data);
        } else {
            if (root.left == null && root.right == null) {
                root = null;
            } else if (root.right == null) {
                root = root.left;
            } else if  (root.left == null) {
                root = root.right;
            } else {
                int newData = getMin(root.right);
                root.data = newData;
                root.right = delete(root.right, newData);
            }
        }
        return root;
    }

    static int getSuccessor(Node root, int data) {
        Node target = findNode(root, data);
        if (target == null) {
            return -1;
        }
        if (target.right != null) {
            return getMin(target.right);
        }
        Node successor = null, ancestor = root;
        while (ancestor != null) {
            if (data < ancestor.data) {
                successor = ancestor;
                ancestor = ancestor.left;
            } else {
                ancestor = ancestor.right;
            }
        }
        if (successor != null) {
            return successor.data;
        }
        return -1;
    }

    static Node findNode(Node root, int data) {
        if (root == null || data == root.data) {
            return root;
        }
        if (data < root.data) {
            return findNode(root.left, data);
        } else {
            return findNode(root.right, data);
        }
    }

    static void printValues(Node root) {
        if (root == null) {
            return;
        }
        printValues(root.left);
        System.out.println(root.data);
        printValues(root.right);
    }

    static int getNodeCount(Node root) {
        if (root == null) {
            return 0;
        }
        return 1 + getNodeCount(root.left) + getNodeCount(root.right);
    }

    public static void main(String[] args) {
        Node root = null;
        root = insert(root, 500);
        root = insert(root, 400);
        root = insert(root, 600);
        root = insert(root, 700);
        root = insert(root, 650);
        root = insert(root, 630);
        root = insert(root, 620);
        root = insert(root, 300);
        root = insert(root, 350);
        root = insert(root, 360);

//        boolean inTree = isInTree(root, 350);
//
//        int min = getMin(root);
//        int max = getMax(root);
//        System.out.println("min: " + min + ", max: " + max);
//
//        int height = getHeight(root);
//        System.out.println("height: " + height);
//
//        boolean isBst = isBst(root);
//        System.out.println(isBst);
//
//        Node newRoot = delete(root, 300);
//        int newMin = getMin(newRoot);
//        System.out.println("newMin: " + newMin);
//
//        int successor = getSuccessor(root, 360);
//        System.out.println("successor: " + successor);

//        printValues(root);

        System.out.println(getNodeCount(root));

    }
}
